package com.mzy.linear_struct.hot100.动态规划;

import java.util.Arrays;

/**
 * @Author: mizy3
 * @Date: 2024/08/11/下午6:33
 * @Description:
 */
public class Pro70爬楼梯 {

    public int climbStairs(int n) {
        if(n == 1) return 1;
        if(n == 2) return 2;

        // 确认dp数组及下标含义
        int[] dp = new int[n + 1];// i 表示第i阶台阶，dp[i] 表示第i阶台阶的跳法
        // 确认递推公式 -> dp[i] = dp[i - 1] +dp[i - 2];
        // 确认初始化值
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        // 遍历顺序 -> 从前到后
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        // 打印数组
        System.out.println(Arrays.toString(dp));
        return dp[n];
    }

    public static void main(String[] args) {
        new Pro70爬楼梯().climbStairs(3);
    }
}























